package main

import (
	"fmt"
	"math/rand"
	"sort"
)

func main() {
	nums := []int{2, 2, 1, 1, 1, 2, 2}
	element := majorityElement5(nums)
	fmt.Printf("%v", element)
}

// 1.排序算法
func majorityElement(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums)/2]
}

// 2.哈希表算法
func majorityElement2(nums []int) int {
	maps := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		maps[nums[i]] = maps[nums[i]] + 1
	}

	var maxKey int
	var maxValue int
	for key, value := range maps {
		if value > maxValue {
			maxValue = value
			maxKey = key
		}
	}
	return maxKey
}

// 3.随机算法
func majorityElement3(nums []int) int {
	var inRange int
	for {
		inRange = GetRandomIntInRange(0, len(nums))
		count := countNums(nums, inRange)
		if count >= (len(nums) / 2) {
			break
		}
	}
	return inRange
}

// GetRandomIntInRange 返回指定范围内的随机整数 [min, max]
func GetRandomIntInRange(min, max int) int {
	// 生成随机数并大于等于 min，小于 max
	return rand.Intn(max-min) + min
}

// 统计元素出现次数
func countNums(nums []int, num int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		if num == nums[i] {
			count++
		}
	}
	return count
}

// 4.分治算法
func majorityElement4(nums []int) int {
	return partition(nums, 0, len(nums)-1)
}

func partition(nums []int, min, max int) int {
	if min == max {
		return nums[min]
	}

	//获取中位数
	mid := (min + max) / 2
	//分治获取最大值
	left := partition(nums, min, mid)
	right := partition(nums, mid+1, max)

	if left == right {
		return left
	}

	leftCount := countNums(nums, left)
	rightCount := countNums(nums, right)

	if leftCount > rightCount {
		return left
	} else {
		return right
	}
}

// 5.Boyer-Moore 投票算法
func majorityElement5(nums []int) int {
	var maxNums int
	tmpl := 0
	for i := 0; i < len(nums); i++ {
		if tmpl == 0 {
			maxNums = nums[i]
		}

		if nums[i] == maxNums {
			tmpl++
		} else {
			tmpl--
		}
	}
	return maxNums
}
